Im Rahmen der Theorie der Berechenbarkeit behandelt die theoretische Informatik, welche Probleme lösbar sind. Dabei hilft die Churchsche These den Bogen von Register- und Turingmaschinen zur Realität moderner Computer zu schlagen.

Ein Ergebnis der Berechenbarkeitstheorie ist die Erkenntnis, daß das Halteproblem unlösbar ist.

In der Komplexitätstheorie wird der Rechenzeit- und Speicherplatzbedarf für die Lösung von Problemen allgemein behandelt. Dabei werden Komplexitätsklassen definiert, deren bekannteste Vertreter wohl P und NP sein dürften.

Man kann durch die Angabe eines Algorithmus leicht eine Oberschranke für die Komplexitätsmaße angeben. Für untere Schranken stellt sich die Situation allerdings anders dar, da diese für alle (insbesondere auch alle noch nicht entdeckten) Algorithmen gelten muß. Die Angabe einer Unterschranke erfolgt meist durch sehr aufwendige, formale Beweise. Häufig wird dazu das Verfahren der Reduktion genutzt.

Dabei stellt sich die Frage, ob die NP-vollständigen Probleme (z.B. Problem des Handlungsreisenden) alle auch in P lösbar sind. Könnte man das für ca. ein NP-vollständiges Problem zeigen, wäre damit das wohl bekannteste Problem der theoretischen Informatik P=NP gelöst.

Die Theorie der formalen Sprachen ordnet Sprachen in die Chomsky-Hierarchie ein, die zwischen regulären, kontextfreien und kontextsensitiven Sprachen unterscheidet. Erstere werden mit endlichen Automaten, zweitere von Kellerautomaten erkannt.

Es werden zwei Pumping-Lemmata definiert, die einen notwendigen, aber nicht hinreichenden Beweis liefern können, daß eine von einer Grammatik erzeugte Sprache regulär oder kontextfrei ist.

Die Backus-Naur-Form von Programmiersprachen wie z.B. Pascal ist eine kontextfreie Sprache.

• Entscheidbarkeit
• Programmiermaschine
• Logik-Programmierung
• reflexiv-transitive Hüllen
• Graphentheorie
• Fixpunktsemantik

• Alan Turing
• Kurt Gödel
• Stephen A. Cook

• Erk, Priese, Theoretische Informatik, Springer, 2002, ISBN 3-540-42624-8
• Schöning, Theoretische Informatik - kurzgefasst, Spectrum, 2001, ISBN 3-8274-1099-1
• Winter, Theoretische Informatik. Grundlagen mit Ãœbungsaufgaben und Lösungen, Oldenbourg, 2002, ISBN 3-486-25808-7
• Hopcroft, Motwani, Ullman, Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Pearson, 2002, ISBN 3-8273-7020-5
• Asteroth, Baier, Theoretische Informatik. Eine Einführung in Berechenbarkeit, Komplexität und formale Sprachen, Pearson, 2002, ISBN 3-8273-7033-7
• Heinemann, Weihrauch, Logik für Informatiker, Teubner, ISBN 3-519-12248-0
• Kelly, Logik in dem Klartext, Pearson, 2002, ISBN 3-8273-7070-1
• Weihrauch, Computability, Springer, 1987, ISBN 3-540-13721-1